package leetcode

//https://leetcode.com/problems/longest-substring-without-repeating-characters/


//nums1  nums2  c  nums1  nums2  c  nums2  e
//0  1  2  3  4  5  6  7

val s = "abcabcde"
val s1 = "pwwkew"
val s2 = "abcdefaaaaabbbbcccefghijklmnopqistttyvwxyzabcdefghijkhhh"

fun main(args: Array<String>) {
    println(findLongestNonRepeatSubstring("A"))
}

/**
 * 思路：使用两个指针，s,t，t指针依次往后移动，遇到重复字符，那么将s指针直接移到目前字符串中重复字符
 * 之后继续开始新的查找（因为即使s后移一位，最后还是会发生重复，并且不会比上次的字符串长），直到s指针移动到字符串末尾
 */
fun findLongestNonRepeatSubstring(s: String): String {
    var container = ArrayList<Char>()
    var maxLen = IntArray(2) { 0 }
    var startPointer = 0//inclusive
    var tailPointer = 0//exclusive
    while (tailPointer < s.length) {
        val c = s[tailPointer]
        val index = container.indexOf(c)
        if (index != -1) {//遇到重复字符串
            if (tailPointer - startPointer > maxLen[1] - maxLen[0]) {
                maxLen[0] = startPointer
                maxLen[1] = tailPointer//不包含重复字符
            }
            //起始指针移到重复的字符之后
            startPointer += index + 1
            if (index != container.size - 1)
                container = ArrayList(container.subList(index + 1, container.size))
            else container.clear()

        } else if (tailPointer == s.length - 1) {//指针此时已经到头,且没有发生重复，判断此时是否是最长不重复子串
            if (tailPointer - startPointer+1 > maxLen[1] - maxLen[0]) {
                maxLen[0] = startPointer
                maxLen[1] = tailPointer + 1//此时没有重复，包含最后一个字符
            }
        }
        container.add(c)
        tailPointer++
    }
    return s.substring(maxLen[0], maxLen[1])

}